{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #4 Keys Keyboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #4键键盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你有一个特殊的键盘包含下面的按键：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>A</code>：在屏幕上打印一个 <code>'A'</code>。</li>\n",
    "\t<li><code>Ctrl-A</code>：选中整个屏幕。</li>\n",
    "\t<li><code>Ctrl-C</code>：复制选中区域到缓冲区。</li>\n",
    "\t<li><code>Ctrl-V</code>：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。</li>\n",
    "</ul>\n",
    "\n",
    "<p>现在，<em>你可以 <strong>最多</strong> 按键 <code>n</code>&nbsp;次（使用上述四种按键），返回屏幕上最多可以显示&nbsp;<code>'A'</code>&nbsp;的个数&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> \n",
    "我们最多可以在屏幕上显示三个'A'通过如下顺序按键：\n",
    "A, A, A\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 7\n",
    "<strong>输出:</strong> 9\n",
    "<strong>解释:</strong> \n",
    "我们最多可以在屏幕上显示九个'A'通过如下顺序按键：\n",
    "A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [4-keys-keyboard](https://leetcode.cn/problems/4-keys-keyboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [4-keys-keyboard](https://leetcode.cn/problems/4-keys-keyboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        # 左边比我小的最远位置, 向前遍历\n",
    "        leftStk = []\n",
    "        leftLT = [-1] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            h = heights[i]\n",
    "            while leftStk and h < heights[leftStk[-1]]:\n",
    "                idx = leftStk.pop()\n",
    "                leftLT[idx] = i\n",
    "            leftStk.append(i)\n",
    "\n",
    "        # 右边比我小的最远位置, 向后遍历\n",
    "        rightStk = []\n",
    "        rightLT = [n] * n\n",
    "        for i in range(n):\n",
    "            h = heights[i]\n",
    "            while rightStk and h < heights[rightStk[-1]]:\n",
    "                idx = rightStk.pop()\n",
    "                rightLT[idx] = i\n",
    "            rightStk.append(i)\n",
    "\n",
    "        maxArea = 0\n",
    "        curArea = 0\n",
    "        for i in range(n):\n",
    "            curArea = heights[i] * (rightLT[i] - leftLT[i] - 1)\n",
    "            maxArea = max(maxArea, curArea)\n",
    "        return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        last_cv_pos = 3\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(last_cv_pos, i-2):\n",
    "                if dp[j]*(i-j-1) > dp[i]:\n",
    "                    dp[i] = dp[j]*(i-j-1)\n",
    "                    last_cv_pos = j\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n<=3:\n",
    "            return n\n",
    "        res=[0,1,2,3]\n",
    "        for i in range(4,n+1):\n",
    "            res.append(max([res[x]*(i-x-1) for x in range(1,i-2)]))\n",
    "            res[-1]=max(res[-1],res[-2]+1)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxA(self, N):\n",
    "        best = [0, 1, 2, 3, 4, 5, 6, 9, 12,\n",
    "                16, 20, 27, 36, 48, 64, 81]\n",
    "        q = (N - 11) // 5 if N > 15 else 0\n",
    "        return best[N - 5*q] * 4**q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, N: int) -> int:\n",
    "\n",
    "        dp = [0 for _ in range(N + 1)]\n",
    "        \n",
    "        for i in range(1, N + 1):\n",
    "            ####情况1：直接敲一个A\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            ####情况2：选中-复制-粘贴\n",
    "            for j in range(i - 1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i-j+1-2))\n",
    "        \n",
    "        return dp[N]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxA(self, N):\n",
    "        best = [0, 1]\n",
    "        for k in range(2, N+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            best[-1] = max(best[-1], best[-2] + 1) #addition\n",
    "        return best[N]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i]表示按键i次最多可以显示的A的个数\n",
    "# 可以选择重新复制一次，或者粘贴上一次复制的内容\n",
    "# max(2 * dp[i-3], dp[i-1]+copy[i])\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        # 如果最后一步按'A': dp[i] = dp[i-1]+1\n",
    "        dp = [0] * (n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(i-1):\n",
    "                dp[i] = max(dp[i], dp[j]*(i-j-1))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [i for i in range(n+1)]\n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            for j in range(i-1):\n",
    "                dp[i] = max(dp[i], dp[j]*(i-j-1))\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(2, min(i, 5)+1):\n",
    "                dp[i] = max(dp[i], dp[i-j]* (j-1))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [i for i in range(n+1)]\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i-1):\n",
    "                dp[i] = max(dp[i], dp[j]*(i-j-1))\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            # 直接一个A\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            # 选择复制粘贴\n",
    "            # 求两步前的最大值\n",
    "            for j in range(i-1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i-j-1))\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1, 2, 3, 4, 5]\n",
    "        for k in range(6, n+1):\n",
    "            #if k<6:\n",
    "                #best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            #else:\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-6, k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0]*(n+2)\n",
    "        if n<7:\n",
    "            return n\n",
    "        dp[0]=0\n",
    "        dp[1]=1\n",
    "        dp[2]=2\n",
    "        dp[3]=3\n",
    "        dp[4]=4\n",
    "        dp[5]=5\n",
    "        dp[6]=6\n",
    "        dp[7]=9\n",
    "        for i in range(8,n+1):\n",
    "            dp[i] = max(dp[i-5]*4,dp[i-4]*3,dp[i-3]*2)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        \n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dp [1] = 1 \n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1] +1 \n",
    "            for j in range(2,n):\n",
    "                dp[i] = max(dp[i],dp[j-2]*(i-j+1))\n",
    "\n",
    "        \n",
    "        \n",
    "        \"\"\"\n",
    "        边界值：\n",
    "\n",
    "        状态转移方程：\n",
    "\n",
    "        \"\"\"\n",
    "        return dp[n]\n",
    "\n",
    "       \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        # index 0 is print A, index 1 is press ctrl-A, index 2 is press ctrl-C, index 3 is press ctrl-V\n",
    "        dp = [[0 for i in range(4)] for j in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] + 1\n",
    "            dp[i][1] = max(dp[i-1][0], dp[i-1][3])\n",
    "            dp[i][2] = dp[i-1][1]\n",
    "            for j in range(3, i):\n",
    "                dp[i][3] = max(dp[i][3], dp[j][2] * (i - j + 1))\n",
    "        return max(dp[-1][0], dp[-1][3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        \n",
    "        # we use dp to represent after i-th move, the max length\n",
    "\n",
    "        dp = [0]*(n+1) # we use n+1 to represent from 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            \n",
    "            dp[i] = dp[i-1] + 1 # when hitting A\n",
    "            # copy and paste at somepoint j\n",
    "            for j in range(i-1): # i-th step is paste, i-1 is copy, j before i-1 is select\n",
    "                dp[i] = max(dp[i], dp[j]*(i-1-j))\n",
    "\n",
    "        return dp[-1]\n",
    "        # # 动态规划，dp[i]表示i次以后的最大数量\n",
    "        # dp = [0] * (n + 1)\n",
    "        # for i in range(1, n + 1):\n",
    "        #     # 可以直接按A\n",
    "        #     dp[i] = dp[i - 1] + 1\n",
    "        #     # 或者从前面复制粘贴得到\n",
    "        #     for j in range(i - 1):\n",
    "        #         # 第j+1步开始，分别进行选中--复制--粘贴的步骤，每粘贴一次就比之间增加了一倍\n",
    "        #         dp[i] = max(dp[i], dp[j] * (i - (j + 1)))\n",
    "        # return dp[n]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # #out of time limit for DFS\n",
    "        # # dirs\n",
    "        # dirs = ('a', 'ca', 'cc', 'cv')\n",
    "\n",
    "        # out = -1000000\n",
    "        # ca_buffer = ''\n",
    "        # cc_buffer = ''\n",
    "        # def dfs(cur_n, cur_res, ca_buffer, cc_buffer): # when have cur_n step left (finished), the result is cur_res\n",
    "            \n",
    "        #     # break\n",
    "        #     if cur_n == 0:\n",
    "        #         nonlocal out\n",
    "        #         out = max(out, len(cur_res))\n",
    "        #         return \n",
    "            \n",
    "        #     if cur_n < 0:\n",
    "        #         return \n",
    "\n",
    "\n",
    "        #     for d in dirs:\n",
    "        #         ncur_res = cur_res\n",
    "        #         ncur_n = cur_n\n",
    "        #         nca_buffer = ca_buffer\n",
    "        #         ncc_buffer = cc_buffer\n",
    "\n",
    "        #         if d == 'a':\n",
    "        #             ncur_res += 'A'\n",
    "                    \n",
    "\n",
    "        #         if d == 'ca':\n",
    "        #             nca_buffer = ncur_res\n",
    "\n",
    "\n",
    "        #         if d == 'cc':\n",
    "        #            ncc_buffer = nca_buffer\n",
    "\n",
    "                \n",
    "        #         if d == 'cv':\n",
    "        #             ncur_res += ncc_buffer\n",
    "\n",
    "        #         dfs(ncur_n-1, ncur_res, nca_buffer, ncc_buffer)\n",
    "\n",
    "\n",
    "        #     return\n",
    "        \n",
    "\n",
    "        # dfs(n, '', '', '')\n",
    "        # return out\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n <= 6: return n\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, 7):\n",
    "            dp[i] = i\n",
    "        \n",
    "        for i in range(7, n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(i-3, 0, -1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i-j-1))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1  # 先尝试着按A键(或者说时按键的次数)\n",
    "            for j in range(2, i):  # 尝试着把刚才按的A键，从第二个开始替换为C-V，从j-2之前都是A键\n",
    "                dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))\n",
    "            \n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0,1]\n",
    "        for i in range(2,n+1):\n",
    "            best.append(max([best[x]* (i-1-x) for x in range(max(i-6,0),i-1)]))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        # 动态规划，dp[i]表示i次以后的最大数量\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            # 可以直接按A\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            # 或者从前面复制粘贴得到\n",
    "            for j in range(i - 1):\n",
    "                # 第j+1步开始，分别进行选中--复制--粘贴的步骤，每粘贴一次就比之间增加了一倍\n",
    "                dp[i] = max(dp[i], dp[j] * (i - (j + 1)))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp=n*[0]\n",
    "        t=0\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                dp[i]= 1\n",
    "            elif i==1:\n",
    "                dp[i]= 2\n",
    "            else:\n",
    "                a=dp[i-1]+1\n",
    "                b=0\n",
    "                for j in range(0,i-2):\n",
    "                    b=max(b,dp[j]*(i-j-1)) \n",
    "\n",
    "                dp[i]=max(a,b)\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "\n",
    "        dp = [0 for i in range(n + 1)]\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            \n",
    "            dp[i] = dp[i-1] + 1\n",
    "\n",
    "            for j in range(1, i-2):\n",
    "                dp[i] = max(dp[i], dp[j] + dp[j] * (i-j-2))\n",
    "        \n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(i - 1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i - (j + 1)))\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [[0 for _ in range(4)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] + 1\n",
    "            dp[i][1] = max(dp[i-1][0], dp[i-1][3])\n",
    "            dp[i][2] = dp[i-1][1]\n",
    "            if i > 3:\n",
    "                for j in range(3, i):\n",
    "                    dp[i][3] = max(dp[i][3], (i-j+1)*dp[j][2])\n",
    "        \n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [[0] * 4 for _ in range(51)]\n",
    "# 初始条件\n",
    "dp[1] = [1, 0, 0, 0]\n",
    "dp[2] = [2, 1, 0, 0]\n",
    "for i in range(3, 51):\n",
    "    # 执行A操作\n",
    "    dp[i][0] = max(dp[i - 1]) + 1\n",
    "    # 执行Ctrl-A操作\n",
    "    dp[i][1] = max(dp[i - 1])\n",
    "    # 执行Ctrl-C操作\n",
    "    dp[i][2] = max(dp[i - 2])\n",
    "    # 执行Ctrl-V操作\n",
    "    dp[i][3] = max(max(dp[j]) * (i - j - 1) for j in range(i - 2))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        return max(dp[n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        # base case\n",
    "        dp[0] = 0\n",
    "        # 对于状态的所有取值\n",
    "        for i in range(1, n + 1):\n",
    "            # 考虑最后是按A键和按C-V键的所有情况，取最大值\n",
    "            # 如果是按A键\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            # 如果是按C-V键，之前必定有C-A, C-C操作不会产生导致dp[i]的增加\n",
    "            # 考虑C-V键出现的位置，贪心地一直按C-V\n",
    "            for j in range(2, i + 1):\n",
    "                dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))  # C-V次数 * C-A时屏幕上A的数量\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1] + 1  # 直接敲一个A\n",
    "            for j in range(i-1): \n",
    "                dp[i] = max(dp[i], dp[j]*(i-j+1-2)) # 尽量使用复制粘贴\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [i for i in range(n+1)]\n",
    "        # dp2 = [0] * n\n",
    "        # for i in range(3, n+1):\n",
    "        #     dp2[i] = dp[i-3]\n",
    "        for i in range(6, n+1):\n",
    "            for j in range(1, i-2):\n",
    "                dp[i] = max(dp[i], dp[i-j-3]*(j+2))\n",
    "        # print(dp)\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 动态规划，dp[i]表示按键次数为i时屏幕显示'A'的次数\n",
    "# 对于每次操作的结果有两种情况\n",
    "# 情况1: 直接打印A \n",
    "#       dp[i] = dp[i - 1] + 1\n",
    "# 情况2: 利用Ctrl-V打印A\n",
    "#       for j in range(1, i - 2):\n",
    "#           dp[i] = max(dp[i], dp[j] + dp[j] * (i - j - 2))\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(1, i - 2):\n",
    "                dp[i] = max(dp[i], dp[j] + dp[j] * (i - j - 2))\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(2, i-2):\n",
    "                dp[i] = max(dp[i], dp[j]*(i-j-1))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            if k<6:\n",
    "                best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            else:\n",
    "                best.append(max(best[x] * (k-x-1) for x in range(k-6, k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [[0]*4 for _ in range(n)]\n",
    "        if n <= 3:\n",
    "            return n\n",
    "        dp[0][0] = 1\n",
    "        dp[1][0] = 2\n",
    "        dp[2][0] = 3\n",
    "        for i in range(3, n):\n",
    "            dp[i][0] = max(dp[i-1])+1\n",
    "            dp[i][1] = dp[i-1][0]\n",
    "            dp[i][2] = dp[i-1][1]\n",
    "            dp[i][3] = max(max(dp[j])*(i-j-1) for j in range(i-2))\n",
    "        # print(dp)\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(1, i - 2):\n",
    "                dp[i] = max(dp[i], dp[j] + dp[j] * (i - j - 2))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxA(self, N):\n",
    "        best = [0, 1, 2]\n",
    "        for k in range(3, N+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-2)))\n",
    "            best[-1] = max(best[-1], best[-2] + 1) #addition\n",
    "        return best[N]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            dp[i]=dp[i-1]+1\n",
    "            if i>=3:\n",
    "                for j in range(3,i+1):\n",
    "                    # print(i,j,dp[i-3],dp[j-3]+dp[i-3]*(i-j))\n",
    "                    # print(dp)\n",
    "                    dp[i]=max(dp[i],dp[j-3]+dp[j-3]*(i-j+1))\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1, 2, 3, 4, 5]\n",
    "        for k in range(6, n+1):\n",
    "            #if k<6:\n",
    "                #best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            #else:\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-6, k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n<=3:return n\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1]+1\n",
    "            for k in range(3,i+1):\n",
    "                dp[i] = max(dp[i],dp[i-k]*(k-1))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        \n",
    "        # we use dp to represent after i-th move, the max length\n",
    "\n",
    "        dp = [0]*(n+1) # we use n+1 to represent from 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            \n",
    "            dp[i] = dp[i-1] + 1 # when hitting A\n",
    "            # copy and paste at somepoint j\n",
    "            for j in range(i-1): # i-th step is paste, i-1 is copy, j before i-1 is select\n",
    "                dp[i] = max(dp[i], dp[j]*(i-1-j))  \n",
    "\n",
    "        return dp[-1]\n",
    "        # # 动态规划，dp[i]表示i次以后的最大数量\n",
    "        # dp = [0] * (n + 1)\n",
    "        # for i in range(1, n + 1):\n",
    "        #     # 可以直接按A\n",
    "        #     dp[i] = dp[i - 1] + 1\n",
    "        #     # 或者从前面复制粘贴得到\n",
    "        #     for j in range(i - 1):\n",
    "        #         # 第j+1步开始，分别进行选中--复制--粘贴的步骤，每粘贴一次就比之间增加了一倍\n",
    "        #         dp[i] = max(dp[i], dp[j] * (i - (j + 1)))\n",
    "        # return dp[n]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # #out of time limit for DFS\n",
    "        # # dirs\n",
    "        # dirs = ('a', 'ca', 'cc', 'cv')\n",
    "\n",
    "        # out = -1000000\n",
    "        # ca_buffer = ''\n",
    "        # cc_buffer = ''\n",
    "        # def dfs(cur_n, cur_res, ca_buffer, cc_buffer): # when have cur_n step left (finished), the result is cur_res\n",
    "            \n",
    "        #     # break\n",
    "        #     if cur_n == 0:\n",
    "        #         nonlocal out\n",
    "        #         out = max(out, len(cur_res))\n",
    "        #         return \n",
    "            \n",
    "        #     if cur_n < 0:\n",
    "        #         return \n",
    "\n",
    "\n",
    "        #     for d in dirs:\n",
    "        #         ncur_res = cur_res\n",
    "        #         ncur_n = cur_n\n",
    "        #         nca_buffer = ca_buffer\n",
    "        #         ncc_buffer = cc_buffer\n",
    "\n",
    "        #         if d == 'a':\n",
    "        #             ncur_res += 'A'\n",
    "                    \n",
    "\n",
    "        #         if d == 'ca':\n",
    "        #             nca_buffer = ncur_res\n",
    "\n",
    "\n",
    "        #         if d == 'cc':\n",
    "        #            ncc_buffer = nca_buffer\n",
    "\n",
    "                \n",
    "        #         if d == 'cv':\n",
    "        #             ncur_res += ncc_buffer\n",
    "\n",
    "        #         dfs(ncur_n-1, ncur_res, nca_buffer, ncc_buffer)\n",
    "\n",
    "\n",
    "        #     return\n",
    "        \n",
    "\n",
    "        # dfs(n, '', '', '')\n",
    "        # return out\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0] * (n + 1)\n",
    "        for k in range(1, n + 1):\n",
    "            best[k] = best[k - 1] + 1\n",
    "            for x in range(k - 1):\n",
    "                best[k] = max(best[k], best[x] * (k - x - 1))\n",
    "        return best[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n):\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = max(dp[i], dp[i - 1] + 1)\n",
    "            for j in range(1, i - 1):\n",
    "                dp[i] = max(dp[i], dp[j - 1] * (i - j))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1,n+1,1):\n",
    "            \n",
    "            dp[i] = dp[i-1] +1\n",
    "            for j in range(2,i+1,1):\n",
    "                if j+2 <= i:\n",
    "                    dp[i] = max(dp[i],dp[j-1] *(i-j))\n",
    "                else:\n",
    "                    break\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n <= 6:\n",
    "            return n\n",
    "        \n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, 7):\n",
    "            dp[i] = i\n",
    "        \n",
    "        for i in range(7, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(1, i - 2):\n",
    "                dp[i] = max(dp[i], dp[i - (j + 2)] * (j + 1))\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[0] = [1, 1]\n",
    "        for i in range(1, n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if i - j < 3:\n",
    "                    dp[i][0] = max(dp[i][0], dp[j][0] + dp[j][1])\n",
    "                else:\n",
    "                    dp[i][0] = max(dp[i][0], (i - j - 1) * dp[j][0])\n",
    "                dp[i][1] = max(dp[i][1], dp[j][1])\n",
    "        print(dp[-1][0])\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            best[-1] = max(best[-1], best[-2] + 1) #addition\n",
    "        return best[n]\n",
    "        \n",
    "    def maxA2(self, n: int) -> int:\n",
    "        best = [0, 1, 2, 3, 4, 5, 6, 9, 12,\n",
    "                16, 20, 27, 36, 48, 64, 81]\n",
    "        q = (n - 11) / 5 if n > 15 else 0\n",
    "        return best[n - 5*q] * 4**q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            best.append(max(best[x] * (k-x-1) for x in range(k)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n<7:\n",
    "            return n\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,7):\n",
    "            dp[i]=i\n",
    "        for i in range(7,n+1):\n",
    "            dp[i]=max(2*dp[i-1]-dp[i-2],2*dp[i-3],3*dp[i-4],4*dp[i-5])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=dp[i-1]+1\n",
    "            for j in range(i-2):\n",
    "                dp[i]=max(dp[i],(i-j-1)*dp[j])\n",
    "        print(dp)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [1,2,3,4,5] + [0]*(n-5)\n",
    "        for i in range(5,n):\n",
    "            dp[i] = max(2*dp[i-3],3*dp[i-4],4*dp[i-5])\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        num_a = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            num_a[i] = num_a[i - 1] + 1\n",
    "            for j in range(i - 1):\n",
    "                num_a[i] = max(num_a[i], num_a[j] * (i - j + 1 - 2))\n",
    "        return num_a[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2, n+1):\n",
    "            if k<6:\n",
    "                best.append(max(best[x] * (k-x-1) for x in range(k-1)))\n",
    "            else:\n",
    "                best.append(max(best[x] * (k-x-1) for x in range(k-6, k-1)))\n",
    "            best[-1] = max(best[-1], best[-2]+1)\n",
    "        return best[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i <= 6:\n",
    "                return i\n",
    "            ans = 0\n",
    "            for j in range(2,i - 2):\n",
    "                # 从第j步开始ctrl-a\n",
    "                ans = max(ans,dfs(j - 1)*(i - (j + 1) + 1))\n",
    "            return ans\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 动态规划，dp[i]表示按键次数为i时屏幕显示'A'的次数\n",
    "# 对于每次操作的结果有两种情况\n",
    "# 情况1: 直接打印A \n",
    "#       dp[i] = dp[i - 1] + 1\n",
    "# 情况2: 利用Ctrl-V打印A\n",
    "#       for j in range(1, i - 2):\n",
    "#           dp[i] = max(dp[i], dp[j] + dp[j] * (i - j - 2))\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        # # 第一种解法\n",
    "        # dp = [0] * (n + 1)\n",
    "        # for i in range(1, n + 1):\n",
    "        #     dp[i] = dp[i - 1] + 1\n",
    "        #     for j in range(1, i - 2):\n",
    "        #         dp[i] = max(dp[i], dp[j] + dp[j] * (i - j - 2))\n",
    "        # return dp[-1]\n",
    "\n",
    "        # 第二种解法\n",
    "        if n <= 6: return n\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, 7):\n",
    "            dp[i] = i\n",
    "        for i in range(7, n + 1):\n",
    "            dp[i] = max(dp[i - 3] * 2, max([dp[j] * (i - j - 1) for j in range(i - 2, 0, -1)]))\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        # 方法一(超时)\n",
    "        # 操作次数、屏幕上A的数量、剪切板A的数量\n",
    "        # 当操作次数为0，a_num就是结果\n",
    "        # 三种情况：打一个A，A加1而剪切板不变。粘贴剪切板，A+剪切板里的数量。全选和复制，两个操作，A的数量不变。\n",
    "        # memo = dict()\n",
    "        # def dp(n, a_num, copy):\n",
    "        #     if n <= 0: return a_num\n",
    "        #     if (n, a_num, copy) in memo: return memo[(n,a_num,copy)]\n",
    "        #     memo[(n,a_num,copu)] = max(dp(n-1, a_num+1, copy), \n",
    "        #                                dp(n-1, a_num+copy, copy),\n",
    "        #                                dp(n-2, a_num, a_num))\n",
    "        #     return memo[(n,a_num,copu)]\n",
    "        # return dp(n, 0, 0)\n",
    "\n",
    "        # 方法二\n",
    "        # dp[i]表示i次操作可以得到的A的数量\n",
    "        # 最后一次操作要么打一个A，要么粘贴C-V\n",
    "        # 当n比较小，全部采用打A比较划算。n比较大，则先打A，再多次选中、复制、粘贴\n",
    "        # dp[0]=0\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1]+1 # 表示此时是打一个A\n",
    "            # 下面判断 粘贴是否比打A更好。遍历前面每一个操作的A数量，对其进行复制（所以是j-2），粘贴(i-j)次\n",
    "            for j in range(2, i):\n",
    "                dp[i] = max(dp[i], dp[j-2]*(i-j+1))\n",
    "        return dp[n]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dpp = [0 for _ in range(n + 1)]\n",
    "        dpp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            dpp[i] = dpp[i - 1] + 1\n",
    "            for j in range(2, i):\n",
    "                dpp[i] = max(dpp[i], dpp[j - 2] * (i - j + 1))\n",
    "        return dpp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n < 5:\n",
    "            return n\n",
    "        memo = [0] * (n + 1)\n",
    "        for i in range(1, 5):\n",
    "            memo[i] = i\n",
    "        for i in range(i, n + 1):\n",
    "            memo[i] = 1 + memo[i - 1]\n",
    "            for j in range(1, i - 2):\n",
    "                memo[i] = max(memo[i], memo[j] * (i - j - 1))\n",
    "        return memo[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n<=3:return n\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1]+1\n",
    "            for k in range(4,i+1):\n",
    "                dp[i] = max(dp[i],dp[i-k]*(k-1))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        best = [0, 1]\n",
    "        for k in range(2,n+1):\n",
    "            best.append(max(best[x]*(k-x-1) for x in range(k-1)))\n",
    "            best[-1] = max(best[-1],best[-2]+1)\n",
    "        return best[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n <= 6: return n\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, 7):\n",
    "            dp[i] = i\n",
    "        \n",
    "        for i in range(7, n+1):\n",
    "            # dp[i] = dp[i-1] + 1\n",
    "            for j in range(i-3, 0, -1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i-j-1))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        \n",
    "        # we use dp to represent after i-th move, the max length\n",
    "\n",
    "        dp = [0]*(n+1) # we use n+1 to represent from 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            \n",
    "            dp[i] = dp[i-1] + 1 # when hitting A\n",
    "            # copy and paste at somepoint j\n",
    "            for j in range(i-1): # i-th step is paste, i-1 is copy, j before i-1 is select\n",
    "                dp[i] = max(dp[i], dp[j]*(i-j-1))\n",
    "\n",
    "        return dp[-1]\n",
    "        # # 动态规划，dp[i]表示i次以后的最大数量\n",
    "        # dp = [0] * (n + 1)\n",
    "        # for i in range(1, n + 1):\n",
    "        #     # 可以直接按A\n",
    "        #     dp[i] = dp[i - 1] + 1\n",
    "        #     # 或者从前面复制粘贴得到\n",
    "        #     for j in range(i - 1):\n",
    "        #         # 第j+1步开始，分别进行选中--复制--粘贴的步骤，每粘贴一次就比之间增加了一倍\n",
    "        #         dp[i] = max(dp[i], dp[j] * (i - (j + 1)))\n",
    "        # return dp[n]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # #out of time limit for DFS\n",
    "        # # dirs\n",
    "        # dirs = ('a', 'ca', 'cc', 'cv')\n",
    "\n",
    "        # out = -1000000\n",
    "        # ca_buffer = ''\n",
    "        # cc_buffer = ''\n",
    "        # def dfs(cur_n, cur_res, ca_buffer, cc_buffer): # when have cur_n step left (finished), the result is cur_res\n",
    "            \n",
    "        #     # break\n",
    "        #     if cur_n == 0:\n",
    "        #         nonlocal out\n",
    "        #         out = max(out, len(cur_res))\n",
    "        #         return \n",
    "            \n",
    "        #     if cur_n < 0:\n",
    "        #         return \n",
    "\n",
    "\n",
    "        #     for d in dirs:\n",
    "        #         ncur_res = cur_res\n",
    "        #         ncur_n = cur_n\n",
    "        #         nca_buffer = ca_buffer\n",
    "        #         ncc_buffer = cc_buffer\n",
    "\n",
    "        #         if d == 'a':\n",
    "        #             ncur_res += 'A'\n",
    "                    \n",
    "\n",
    "        #         if d == 'ca':\n",
    "        #             nca_buffer = ncur_res\n",
    "\n",
    "\n",
    "        #         if d == 'cc':\n",
    "        #            ncc_buffer = nca_buffer\n",
    "\n",
    "                \n",
    "        #         if d == 'cv':\n",
    "        #             ncur_res += ncc_buffer\n",
    "\n",
    "        #         dfs(ncur_n-1, ncur_res, nca_buffer, ncc_buffer)\n",
    "\n",
    "\n",
    "        #     return\n",
    "        \n",
    "\n",
    "        # dfs(n, '', '', '')\n",
    "        # return out\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1]+1\n",
    "            for j in range(2, i):\n",
    "                dp[i] = max(dp[i], dp[j-2]*(i-j+1))\n",
    "        return dp[n]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(i - 1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i - j + 1 - 2))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return n\n",
    "        dpp = [0 for _ in range(n + 1)]\n",
    "        dpp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            dpp[i] = dpp[i - 1] + 1\n",
    "            for j in range(2, i):\n",
    "                dpp[i] = max(dpp[i], dpp[j - 2] * (i - j + 1))\n",
    "        return max(dpp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        @functools.cache\n",
    "        def f(n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            elif n <= 0:\n",
    "                return 0\n",
    "            ret = f(n-1)+1\n",
    "            for x in range(n-2):\n",
    "                ret = max(ret, f(x)*(n-x-1))\n",
    "            return ret\n",
    "\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(2, i-2):\n",
    "                dp[i] = max(dp[i], dp[j]*(i-j-1))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def maxA(self, n: int) -> int:\n",
    "        if n < 7:\n",
    "            return n\n",
    "        ans = n\n",
    "        for i in range(1, n - 2):\n",
    "            ans = max(ans, self.maxA(i) * (n - i - 1))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, n: int) -> int:\n",
    "        dp = [[0] * 4 for _ in range(51)]\n",
    "        # 初始条件\n",
    "        dp[1] = [1, 0, 0, 0]\n",
    "        dp[2] = [2, 1, 0, 0]\n",
    "        for i in range(3, 51):\n",
    "            # 执行A操作\n",
    "            dp[i][0] = max(dp[i - 1]) + 1\n",
    "            # 执行Ctrl-A操作\n",
    "            dp[i][1] = max(dp[i - 1])\n",
    "            # 执行Ctrl-C操作\n",
    "            dp[i][2] = max(dp[i - 2])\n",
    "            # 执行Ctrl-V操作 # why \n",
    "            dp[i][3] = max(max(dp[j]) * (i - j - 1) for j in range(i - 2))\n",
    "\n",
    "        return max(dp[n])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # out of time limit for DFS\n",
    "        # # dirs\n",
    "        # dirs = ('a', 'ca', 'cc', 'cv')\n",
    "\n",
    "        # out = -1000000\n",
    "        # ca_buffer = ''\n",
    "        # cc_buffer = ''\n",
    "        # def dfs(cur_n, cur_res, ca_buffer, cc_buffer): # when have cur_n step left (finished), the result is cur_res\n",
    "            \n",
    "        #     # break\n",
    "        #     if cur_n == 0:\n",
    "        #         nonlocal out\n",
    "        #         out = max(out, len(cur_res))\n",
    "        #         return \n",
    "            \n",
    "        #     if cur_n < 0:\n",
    "        #         return \n",
    "\n",
    "\n",
    "        #     for d in dirs:\n",
    "        #         ncur_res = cur_res\n",
    "        #         ncur_n = cur_n\n",
    "        #         nca_buffer = ca_buffer\n",
    "        #         ncc_buffer = cc_buffer\n",
    "\n",
    "        #         if d == 'a':\n",
    "        #             ncur_res += 'A'\n",
    "                    \n",
    "\n",
    "        #         if d == 'ca':\n",
    "        #             nca_buffer = ncur_res\n",
    "\n",
    "\n",
    "        #         if d == 'cc':\n",
    "        #            ncc_buffer = nca_buffer\n",
    "\n",
    "                \n",
    "        #         if d == 'cv':\n",
    "        #             ncur_res += ncc_buffer\n",
    "\n",
    "        #         dfs(ncur_n-1, ncur_res, nca_buffer, ncc_buffer)\n",
    "\n",
    "\n",
    "        #     return\n",
    "        \n",
    "\n",
    "        # dfs(n, '', '', '')\n",
    "        # return out\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxA(self, N: int) -> int:\n",
    "        dp = [0 for _ in range(N + 1)]\n",
    "        \n",
    "        for i in range(1, N + 1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(i - 1):\n",
    "                dp[i] = max(dp[i], dp[j] * (i-j+1-2))\n",
    "        \n",
    "        return dp[N]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
